<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <!-- 这是一个受限的线性结构 -->
    <title>栈结构-Stack</title>
    特点：
    1. 先进后出 LIFO
    2. 只能在表的后端添加元素
    3. 只能在表的后端删除元素
</head>

<body>
    <script>
        // 封装一个栈结构
        class Stack {
            constructor() {
                this.items = []
            }
            // 入栈
            push(item) {
                this.items.push(item)
            }
            // 出栈
            pop() {
                return this.items.pop()
            }
            // 栈内元素长度
            size() {
                return this.items.length
            }
            // 当前栈是否为空
            isEmpty() {
                return this.items.length == 0
            }
            toString() {
                var resultStr = ''
                for (let i = 0; i < this.items.length; i++) {
                    resultStr += this.items[i] + ''
                }
                return resultStr
            }
        }

        /*
            栈结构例子：十进制转二进制
        */
        const stack = new Stack()
        // 10进制转2进制
        function dec2bit(decNumber) {
            while (decNumber > 0) {
                stack.push(decNumber % 2)
                decNumber = Math.floor(decNumber / 2)
            }
            let str = ''
            while (!stack.isEmpty()) {
                str += stack.pop()
            }
            return str
        }
        let result = dec2bit(100)
        console.log(result)
    </script>

    <script>
        // 词法分析的时候，经常会用到"栈"这个数据结构
        // 后进先出：Last In First Out（LIFO）
        // 先进后出：First In Last Out (FILO)
        // 在JS中，栈可以用数组模拟，需要限制只能使用push()和pop(),不能使用unshift()和shift()

        // **************************************************************
        // 编写“只能重复”smartRepeat函数，实现：
        // 将'3[abc]'变为'abcabcabc'
        // 将'3[2[a]2[b]]'变为'aabbaabbaabb'
        // 将'2[1[a]3[b]2[3[c]4[d]]]'变为'abbbcccddddcccddddabbbcccddddcccdddd'

        // 解题思路：
        // 1. 遍历字符串的每一个字符
        // 2. 如果这个字符是数字，则将数字压入到“数字栈”中，将空字符串压入到“字符栈”中
        // 3. 如果这个字符是字母，则“字符栈”的栈顶那一项改为这个字母
        // 4. 如果这个字符是”]“，则将’数字栈‘、’字符栈‘弹栈，得到弹出来的字符重复数字栈弹出的数字的次数
        // 5. 将第4步操作的返回值的字符串替换”字符栈“栈顶的字符
        // 6. 最终两个栈内都只剩下最后一项，分别为数字和字符
        // 7. 将两个栈内的元素进行repeat，即可获得最终的字符串
        const str = '2[1[a]3[b]2[3[c]4[d]]]'

        function smartRepeat(templateStr) {
            let index = 0
            let numStack = []
            let charStack = []
            while (index < templateStr.length - 1) {
                let rest = templateStr.substring(index)
                if (/^\d+\[/.test(rest)) {
                    // 判断是否为数字
                    let times = rest.match(/^(\d+)\[/)[1]
                    index += times.toString().length + 1
                    numStack.push(times)
                    charStack.push('')
                } else if (/^\w+]/.test(rest)) {
                    // 判断是否为字母
                    let word = rest.match(/^(\w+)\]/)[1]
                    charStack[charStack.length - 1] = word
                    index += word.length
                } else if (rest[0] == ']') {
                    let times = numStack.pop()
                    let word = charStack.pop()
                    charStack[charStack.length - 1] += word.repeat(times)
                    index++
                }
                console.log(index, numStack, charStack)
            }
            return charStack[0].repeat(numStack[0])
        }
        console.log(smartRepeat(str))
    </script>

    <script>
        class Stack1 {
            constructor() {
                this.items = []
                this.push(item) {
                    this.items.push(item)
                }
                this.pop() {
                    return this.items.pop()
                }
                this.isEmpty() {
                    return this.items.length == 0 ? true : false
                }
                this.size() {
                    return this.items.length
                }
            }
        }
        const stack1 = new Stack1()

        function des2bit(desNumber) {
            while (desNumber > 0) {
                stack1.items.push(desNumber % 2)
                desNumber = Math.floor(desNumber / 2)
            }
            let bitStr = ''
            while (!stack1.isEmpty()) {
                bitStr += stack1.pop()
            }
            return bitStr
        }
        console.log(des2bit(1000))
    </script>
</body>

</html>